class Solution1289 {
    int[][] dpArr;
    public int[] getTwoMin(int[] tmpArr){
        int Min=Integer.MAX_VALUE;
        int secMin=Integer.MAX_VALUE;
        int minInd=-1;
        for (int i = 0; i < tmpArr.length; i++) {
            int tmpNum=tmpArr[i];
            if(tmpNum<Min){
                secMin=Min;
                Min=tmpNum;
                minInd=i;
            }
            else if(tmpNum<secMin){
                secMin=tmpNum;
            }
        }
        return new int[] {Min,secMin,minInd};
    }

    public int minFallingPathSum(int[][] arr) {
        int n=arr.length;
        int m=arr[0].length;
        dpArr=new int[n][m];
        for (int i = 0; i < m; i++) {
            dpArr[0][i]=arr[0][i];
        }
        for (int i = 1; i < n; i++) {
            int[] minArr=getTwoMin(dpArr[i-1]);
            for (int j = 0; j < m; j++) {
                if(j==minArr[2]){
                    dpArr[i][j]=minArr[1]+arr[i][j];
                }
                else{
                    dpArr[i][j]=minArr[0]+arr[i][j];
                }
            }
        }
        return getTwoMin(dpArr[dpArr.length-1])[0];
    }


    public static void main(String[] args) {
        Solution1289 s=new Solution1289();
        System.out.println(s.minFallingPathSum(new int[][]
                {{-73,61,43,-48,-36},{3,30,27,57,10},{96,-76,84,59,-15},{5,-49,76,31,-7},{97,91,61,-46,67}} ));
    }
}
